home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / scfe.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  14.8 KB  |  531 lines
  1. /* Copyright (C) 1992, 1995, 1997, 1998, 1999 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: scfe.c,v 1.2 2000/09/19 19:00:48 lpd Exp $ */
  20. /* CCITTFax encoding filter */
  21. #include "stdio_.h"        /* includes std.h */
  22. #include "memory_.h"
  23. #include "gdebug.h"
  24. #include "strimpl.h"
  25. #include "scf.h"
  26. #include "scfx.h"
  27.  
  28. /* ------ Macros and support routines ------ */
  29.  
  30. /* Statistics */
  31.  
  32. #ifdef DEBUG
  33.  
  34. typedef struct stats_runs_s {
  35.     ulong termination[64];
  36.     ulong make_up[41];
  37. } stats_runs_t;
  38. private stats_runs_t stats_white_runs, stats_black_runs;
  39.  
  40. #define COUNT_RUN(tab, i) (tab)[i]++;
  41.  
  42. private void
  43. print_run_stats(const stats_runs_t * stats)
  44. {
  45.     int i;
  46.     ulong total;
  47.  
  48.     for (i = 0, total = 0; i < 41; i++)
  49.     dprintf1(" %lu", stats->make_up[i]),
  50.         total += stats->make_up[i];
  51.     dprintf1(" total=%lu\n\t", total);
  52.     for (i = 0, total = 0; i < 64; i++)
  53.     dprintf1(" %lu", stats->termination[i]),
  54.         total += stats->termination[i];
  55.     dprintf1(" total=%lu\n", total);
  56. }
  57.  
  58. #else /* !DEBUG */
  59.  
  60. #define COUNT_RUN(cnt, i) DO_NOTHING
  61.  
  62. #endif /* DEBUG */
  63.  
  64. /* Put a run onto the output stream. */
  65. /* Free variables: q, bits, bits_left. */
  66.  
  67. #define CF_PUT_RUN(ss, lenv, rt, stats)\
  68. BEGIN\
  69.     cfe_run rr;\
  70. \
  71.     if ( lenv >= 64 ) {\
  72.     hce_store_state();\
  73.     q = cf_put_long_run(ss, q, lenv, &rt);\
  74.     hce_load_state();\
  75.     lenv &= 63;\
  76.     }\
  77.     rr = rt.termination[lenv];\
  78.     COUNT_RUN(stats.termination, lenv);\
  79.     hc_put_value(ss, q, rr.code, rr.code_length);\
  80. END
  81.  
  82. private byte *
  83. cf_put_long_run(stream_CFE_state * ss, byte * q, int lenv, const cf_runs * prt)
  84. {
  85.     hce_declare_state;
  86.     cfe_run rr;
  87.  
  88. #ifdef DEBUG
  89.     stats_runs_t *pstats =
  90.     (prt == &cf_white_runs ? &stats_white_runs : &stats_black_runs);
  91.  
  92. #endif
  93.  
  94.     hce_load_state();
  95.     while (lenv >= 2560 + 64) {
  96.     rr = prt->make_up[40];
  97.     COUNT_RUN(pstats->make_up, 40);
  98.     hc_put_value(ss, q, rr.code, rr.code_length);
  99.     lenv -= 2560;
  100.     }
  101.     rr = prt->make_up[lenv >> 6];
  102.     COUNT_RUN(pstats->make_up, lenv >> 6);
  103.     hc_put_value(ss, q, rr.code, rr.code_length);
  104.     hce_store_state();
  105.     return q;
  106. }
  107.  
  108. #define CF_PUT_WHITE_RUN(ss, lenv)\
  109.   CF_PUT_RUN(ss, lenv, cf_white_runs, stats_white_runs)
  110.  
  111. #define CF_PUT_BLACK_RUN(ss, lenv)\
  112.   CF_PUT_RUN(ss, lenv, cf_black_runs, stats_black_runs)
  113.  
  114. /* ------ CCITTFaxEncode ------ */
  115.  
  116. private_st_CFE_state();
  117.  
  118. private void s_CFE_release(P1(stream_state *));
  119.  
  120. /* Set default parameter values. */
  121. private void
  122. s_CFE_set_defaults(register stream_state * st)
  123. {
  124.     stream_CFE_state *const ss = (stream_CFE_state *) st;
  125.  
  126.     s_CFE_set_defaults_inline(ss);
  127. }
  128.  
  129. /* Initialize CCITTFaxEncode filter */
  130. private int
  131. s_CFE_init(register stream_state * st)
  132. {
  133.     stream_CFE_state *const ss = (stream_CFE_state *) st;
  134.     int columns = ss->Columns;
  135.  
  136.     /*
  137.      * The worst case for encoding is alternating white and black pixels.
  138.      * For 1-D encoding, the worst case is 9 bits per 2 pixels; for 2-D
  139.      * (horizontal), 12 bits per 2 pixels.  To fill out a scan line,
  140.      * we may add up to 6 12-bit EOL codes.
  141.      */
  142.     int code_bytes =
  143.     ((columns * (ss->K == 0 ? 9 : 12)) >> 4) + 20;    /* add slop */
  144.     int raster = ss->raster =
  145.     ROUND_UP((columns + 7) >> 3, ss->DecodedByteAlign);
  146.  
  147.     s_hce_init_inline(ss);
  148.     ss->lbuf = ss->lprev = ss->lcode = 0;    /* in case we have to release */
  149.     if (columns > cfe_max_width)
  150.     return ERRC;
  151. /****** WRONG ******/
  152.     /* Because skip_white_pixels can look as many as 4 bytes ahead, */
  153.     /* we need to allow 4 extra bytes at the end of the row buffers. */
  154.     ss->lbuf = gs_alloc_bytes(st->memory, raster + 4, "CFE lbuf");
  155.     ss->lcode = gs_alloc_bytes(st->memory, code_bytes, "CFE lcode");
  156.     if (ss->lbuf == 0 || ss->lcode == 0) {
  157.     s_CFE_release(st);
  158.     return ERRC;
  159. /****** WRONG ******/
  160.     }
  161.     if (ss->K != 0) {
  162.     ss->lprev = gs_alloc_bytes(st->memory, raster + 4, "CFE lprev");
  163.     if (ss->lprev == 0) {
  164.         s_CFE_release(st);
  165.         return ERRC;
  166. /****** WRONG ******/
  167.     }
  168.     /* Clear the initial reference line for 2-D encoding. */
  169.     /* Make sure it is terminated properly. */
  170.     memset(ss->lprev, (ss->BlackIs1 ? 0 : 0xff), raster);
  171.     if (columns & 7)
  172.         ss->lprev[raster - 1] ^= 0x80 >> (columns & 7);
  173.     else
  174.         ss->lprev[raster] = ~ss->lprev[0];
  175.     }
  176.     ss->read_count = raster;
  177.     ss->write_count = 0;
  178.     ss->k_left = (ss->K > 0 ? 1 : ss->K);
  179.     ss->max_code_bytes = code_bytes;
  180.     return 0;
  181. }
  182.  
  183. /* Release the filter. */
  184. private void
  185. s_CFE_release(stream_state * st)
  186. {
  187.     stream_CFE_state *const ss = (stream_CFE_state *) st;
  188.  
  189.     gs_free_object(st->memory, ss->lprev, "CFE lprev(close)");
  190.     gs_free_object(st->memory, ss->lcode, "CFE lcode(close)");
  191.     gs_free_object(st->memory, ss->lbuf, "CFE lbuf(close)");
  192. }
  193.  
  194. /* Flush the buffer */
  195. private void cf_encode_1d(P3(stream_CFE_state *, const byte *,
  196.                  stream_cursor_write *));
  197. private void cf_encode_2d(P4(stream_CFE_state *, const byte *,
  198.                  stream_cursor_write *, const byte *));
  199. private int
  200. s_CFE_process(stream_state * st, stream_cursor_read * pr,
  201.           stream_cursor_write * pw, bool last)
  202. {
  203.     stream_CFE_state *const ss = (stream_CFE_state *) st;
  204.     const byte *rlimit = pr->limit;
  205.     byte *wlimit = pw->limit;
  206.     int raster = ss->raster;
  207.     byte end_mask = 1 << (-ss->Columns & 7);
  208.     int status = 0;
  209.  
  210.     for (;;) {
  211.     stream_cursor_write w;
  212.  
  213.     if_debug2('w', "[w]CFE: read_count = %d, write_count=%d,\n",
  214.           ss->read_count, ss->write_count);
  215.     if_debug6('w', "    pr = 0x%lx(%d)0x%lx, pw = 0x%lx(%d)0x%lx\n",
  216.           (ulong) pr->ptr, (int)(rlimit - pr->ptr), (ulong) rlimit,
  217.           (ulong) pw->ptr, (int)(wlimit - pw->ptr), (ulong) wlimit);
  218.     if (ss->write_count) {
  219.         /* Copy more of an encoded line to the caller. */
  220.         int wcount = wlimit - pw->ptr;
  221.         int ccount = min(wcount, ss->write_count);
  222.  
  223.         memcpy(pw->ptr + 1, ss->lcode + ss->code_bytes - ss->write_count,
  224.            ccount);
  225.         pw->ptr += ccount;
  226.         if ((ss->write_count -= ccount) > 0) {
  227.         status = 1;
  228.         break;
  229.         }
  230.     }
  231.     if (ss->read_count) {
  232.         /* Copy more of an unencoded line from the caller. */
  233.         int rcount = rlimit - pr->ptr;
  234.         int ccount = min(rcount, ss->read_count);
  235.  
  236.         if (rcount == 0 && last)
  237.         break;
  238.         memcpy(ss->lbuf + raster - ss->read_count,
  239.            pr->ptr + 1, ccount);
  240.         pr->ptr += ccount;
  241.         if ((ss->read_count -= ccount) != 0)
  242.         break;
  243.     }
  244.     /*
  245.      * We have a full scan line in lbuf.  Ensure that it ends with
  246.      * two polarity changes.
  247.      */
  248.     {
  249.         byte *end = ss->lbuf + raster - 1;
  250.         byte end_bit = *end & end_mask;
  251.         byte not_bit = end_bit ^ end_mask;
  252.  
  253.         *end &= -end_mask;
  254.         if (end_mask == 1)
  255.         end[1] = (end_bit ? 0x40 : 0x80);
  256.         else if (end_mask == 2)
  257.         *end |= not_bit >> 1, end[1] = end_bit << 7;
  258.         else
  259.         *end |= (not_bit >> 1) | (end_bit >> 2);
  260.     }
  261.     /*
  262.      * Write the output directly to the caller's buffer if it's large
  263.      * enough, otherwise to our own buffer.
  264.      */
  265.     if (wlimit - pw->ptr >= ss->max_code_bytes) {
  266.         w = *pw;
  267.     } else {
  268.         w.ptr = ss->lcode - 1;
  269.         w.limit = w.ptr + ss->max_code_bytes;
  270.     }
  271. #ifdef DEBUG
  272.     if (ss->K > 0) {
  273.         if_debug1('w', "[w]new row, k_left=%d\n",
  274.               ss->k_left);
  275.     } else {
  276.         if_debug0('w', "[w]new row\n");
  277.     }
  278. #endif
  279.     /*
  280.      * Write an EOL (actually a "beginning of line") if requested.
  281.      */
  282.     if (ss->EndOfLine) {
  283.         const cfe_run *rp =
  284.         (ss->K <= 0 ? &cf_run_eol :
  285.          ss->k_left > 1 ? &cf2_run_eol_2d :
  286.          &cf2_run_eol_1d);
  287.         cfe_run run;
  288.  
  289.         hce_declare_state;
  290.  
  291.         hce_load_state();
  292.         if (ss->EncodedByteAlign) {
  293.         run = *rp;
  294.         /* Pad the run on the left */
  295.         /* so it winds up byte-aligned. */
  296.         run.code_length +=
  297.             (bits_left - run_eol_code_length) & 7;
  298.         if (run.code_length > 16)    /* <= 23 */
  299.             bits_left -= run.code_length & 7,
  300.             run.code_length = 16;
  301.         rp = &run;
  302.         }
  303.         hc_put_code(ss, w.ptr, rp);
  304.         hce_store_state();
  305.     } else if (ss->EncodedByteAlign)
  306.         ss->bits_left &= ~7;
  307.     /* Encode the line. */
  308.     if (ss->K == 0)
  309.         cf_encode_1d(ss, ss->lbuf, &w);    /* pure 1-D */
  310.     else if (ss->K < 0)
  311.         cf_encode_2d(ss, ss->lbuf, &w, ss->lprev);    /* pure 2-D */
  312.     else if (--(ss->k_left))    /* mixed, use 2-D */
  313.         cf_encode_2d(ss, ss->lbuf, &w, ss->lprev);
  314.     else {            /* mixed, use 1-D */
  315.         cf_encode_1d(ss, ss->lbuf, &w);
  316.         ss->k_left = ss->K;
  317.     }
  318.     /*
  319.      * If we didn't write directly to the client's buffer, schedule
  320.      * the output data to be written.
  321.      */
  322.     if (w.limit == wlimit)
  323.         pw->ptr = w.ptr;
  324.     else
  325.         ss->write_count = ss->code_bytes = w.ptr - (ss->lcode - 1);
  326.     if (ss->K != 0) {
  327.         /* In 2-D modes, swap the current and previous scan lines. */
  328.         byte *temp = ss->lbuf;
  329.  
  330.         ss->lbuf = ss->lprev;
  331.         ss->lprev = temp;
  332.     }
  333.     /* Note that the input buffer needs refilling. */
  334.     ss->read_count = raster;
  335.     }
  336.     /*
  337.      * When we exit from the loop, we know that write_count = 0, and
  338.      * there is no line waiting to be processed in the input buffer.
  339.      */
  340.     if (last && status == 0) {
  341.     const cfe_run *rp =
  342.     (ss->K > 0 ? &cf2_run_eol_1d : &cf_run_eol);
  343.     int i = (!ss->EndOfBlock ? 0 : ss->K < 0 ? 2 : 6);
  344.     uint bits_to_write =
  345.     hc_bits_size - ss->bits_left + i * rp->code_length;
  346.     byte *q = pw->ptr;
  347.  
  348.     hce_declare_state;
  349.  
  350.     if (wlimit - q < (bits_to_write + 7) >> 3) {
  351.         status = 1;
  352.         goto out;
  353.     }
  354.     hce_load_state();
  355.     if (ss->EncodedByteAlign)
  356.         bits_left &= ~7;
  357.     while (--i >= 0)
  358.         hc_put_code(ss, q, rp);
  359.     /* Force out the last byte or bytes. */
  360.     pw->ptr = hc_put_last_bits((stream_hc_state *) ss, q);
  361.     }
  362.   out:
  363.     if_debug9('w', "[w]CFE exit %d: read_count = %d, write_count = %d,\n     pr = 0x%lx(%d)0x%lx; pw = 0x%lx(%d)0x%lx\n",
  364.           status, ss->read_count, ss->write_count,
  365.           (ulong) pr->ptr, (int)(rlimit - pr->ptr), (ulong) rlimit,
  366.           (ulong) pw->ptr, (int)(wlimit - pw->ptr), (ulong) wlimit);
  367. #ifdef DEBUG
  368.     if (pr->ptr > rlimit || pw->ptr > wlimit) {
  369.     lprintf("Pointer overrun!\n");
  370.     status = ERRC;
  371.     }
  372.     if (gs_debug_c('w') && status == 1) {
  373.     dlputs("[w]white runs:");
  374.     print_run_stats(&stats_white_runs);
  375.     dlputs("[w]black runs:");
  376.     print_run_stats(&stats_black_runs);
  377.     }
  378. #endif
  379.     return status;
  380. }
  381.  
  382. /* Encode a 1-D scan line. */
  383. private void
  384. cf_encode_1d(stream_CFE_state * ss, const byte * lbuf, stream_cursor_write * pw)
  385. {
  386.     uint count = ss->raster << 3;
  387.     byte *q = pw->ptr;
  388.     int end_count = -ss->Columns & 7;
  389.     int rlen;
  390.  
  391.     hce_declare_state;
  392.     const byte *p = lbuf;
  393.     byte invert = (ss->BlackIs1 ? 0 : 0xff);
  394.  
  395.     /* Invariant: data = p[-1] ^ invert. */
  396.     uint data = *p++ ^ invert;
  397.  
  398.     hce_load_state();
  399.     while (count != end_count) {
  400.     /* Parse a white run. */
  401.     skip_white_pixels(data, p, count, invert, rlen);
  402.     CF_PUT_WHITE_RUN(ss, rlen);
  403.     if (count == end_count)
  404.         break;
  405.     /* Parse a black run. */
  406.     skip_black_pixels(data, p, count, invert, rlen);
  407.     CF_PUT_BLACK_RUN(ss, rlen);
  408.     }
  409.     hce_store_state();
  410.     pw->ptr = q;
  411. }
  412.  
  413. /* Encode a 2-D scan line. */
  414. private void
  415. cf_encode_2d(stream_CFE_state * ss, const byte * lbuf, stream_cursor_write * pw,
  416.          const byte * lprev)
  417. {
  418.     byte invert_white = (ss->BlackIs1 ? 0 : 0xff);
  419.     byte invert = invert_white;
  420.     uint count = ss->raster << 3;
  421.     int end_count = -ss->Columns & 7;
  422.     const byte *p = lbuf;
  423.     byte *q = pw->ptr;
  424.     uint data = *p++ ^ invert;
  425.  
  426.     hce_declare_state;
  427.     /*
  428.      * In order to handle the nominal 'changing white' at the beginning of
  429.      * each scan line, we need to suppress the test for an initial black bit
  430.      * in the reference line when we are at the very beginning of the scan
  431.      * line.  To avoid an extra test, we use two different mask tables.
  432.      */
  433.     static const byte initial_count_bit[8] =
  434.     {
  435.     0, 1, 2, 4, 8, 0x10, 0x20, 0x40
  436.     };
  437.     static const byte further_count_bit[8] =
  438.     {
  439.     0x80, 1, 2, 4, 8, 0x10, 0x20, 0x40
  440.     };
  441.     const byte *count_bit = initial_count_bit;
  442.  
  443.     hce_load_state();
  444.     while (count != end_count) {
  445.     /*
  446.      * If invert == invert_white, white and black have their
  447.      * correct meanings; if invert == ~invert_white,
  448.      * black and white are interchanged.
  449.      */
  450.     uint a0 = count;
  451.     uint a1;
  452.  
  453. #define b1 (a1 - diff)        /* only for printing */
  454.     int diff;
  455.     uint prev_count = count;
  456.     const byte *prev_p = p - lbuf + lprev;
  457.     byte prev_data = prev_p[-1] ^ invert;
  458.     int rlen;
  459.  
  460.     /* Find the a1 and b1 transitions. */
  461.     skip_white_pixels(data, p, count, invert, rlen);
  462.     a1 = count;
  463.     if ((prev_data & count_bit[prev_count & 7])) {
  464.         /* Look for changing white first. */
  465.         skip_black_pixels(prev_data, prev_p, prev_count, invert, rlen);
  466.     }
  467.     count_bit = further_count_bit;    /* no longer at beginning */
  468.       pass:
  469.     if (prev_count != end_count)
  470.         skip_white_pixels(prev_data, prev_p, prev_count, invert, rlen);
  471.     diff = a1 - prev_count;    /* i.e., logical b1 - a1 */
  472.     /* In all the comparisons below, remember that count */
  473.     /* runs downward, not upward, so the comparisons are */
  474.     /* reversed. */
  475.     if (diff <= -2) {
  476.         /* Could be a pass mode.  Find b2. */
  477.         if (prev_count != end_count)
  478.         skip_black_pixels(prev_data, prev_p,
  479.                   prev_count, invert, rlen);
  480.         if (prev_count > a1) {
  481.         /* Use pass mode. */
  482.         if_debug4('W', "[W]pass: count = %d, a1 = %d, b1 = %d, new count = %d\n",
  483.               a0, a1, b1, prev_count);
  484.         hc_put_value(ss, q, cf2_run_pass_value, cf2_run_pass_length);
  485.         a0 = prev_count;
  486.         goto pass;
  487.         }
  488.     }
  489.     /* Check for vertical coding. */
  490.     if (diff <= 3 && diff >= -3) {
  491.         /* Use vertical coding. */
  492.         const cfe_run *cp = &cf2_run_vertical[diff + 3];
  493.  
  494.         if_debug5('W', "[W]vertical %d: count = %d, a1 = %d, b1 = %d, new count = %d\n",
  495.               diff, a0, a1, b1, count);
  496.         hc_put_code(ss, q, cp);
  497.         invert = ~invert;    /* a1 polarity changes */
  498.         data ^= 0xff;
  499.         continue;
  500.     }
  501.     /* No luck, use horizontal coding. */
  502.     if (count != end_count)
  503.         skip_black_pixels(data, p, count, invert, rlen);    /* find a2 */
  504.     hc_put_value(ss, q, cf2_run_horizontal_value,
  505.              cf2_run_horizontal_length);
  506.     a0 -= a1;
  507.     a1 -= count;
  508.     if (invert == invert_white) {
  509.         if_debug3('W', "[W]horizontal: white = %d, black = %d, new count = %d\n",
  510.               a0, a1, count);
  511.         CF_PUT_WHITE_RUN(ss, a0);
  512.         CF_PUT_BLACK_RUN(ss, a1);
  513.     } else {
  514.         if_debug3('W', "[W]horizontal: black = %d, white = %d, new count = %d\n",
  515.               a0, a1, count);
  516.         CF_PUT_BLACK_RUN(ss, a0);
  517.         CF_PUT_WHITE_RUN(ss, a1);
  518. #undef b1
  519.     }
  520.     }
  521.     hce_store_state();
  522.     pw->ptr = q;
  523. }
  524.  
  525. /* Stream template */
  526. const stream_template s_CFE_template =
  527. {
  528.     &st_CFE_state, s_CFE_init, s_CFE_process, 1, 1,
  529.     s_CFE_release, s_CFE_set_defaults
  530. };
  531.